package com.atcumt.Write.sort;

import java.util.Arrays;

/**
 * 冒泡排序算法: 时间复杂度：O(n^2)
 *
 * 比较相邻元素，如果第一个比第二个大，则交换他们
 * 一轮下来，可以保证最后一个数是最大的
 * 执行 n-1 轮，就可以完成排序
 */
public class BubbleSort {

    public static void main(String[] args) {

        int[] data = {4, 5, 6, 3, 2, 1, 10};
        System.out.println("排序前：" + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("排序后：" + Arrays.toString(data));
    }

    private static void bubbleSort (int[] arr) {

        int n = arr.length - 1;

        for (int i = 0; i < n; i++) {  // 排序次数
            boolean flag = false;   // 每轮排序开始之前置空 flag

            for (int j = 0; j < n - i; j++) {  // 冒泡排序次数：n - i
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];  // 两两交换
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }

            }
            if (!flag) {
                break; // 在一次排序中，无交换项产生，说明排序结束
            }
        }
    }

}
